package work.algorithm.image01;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 广度优先遍历
 * Breadth-First-Search
 * BFS
 */
public class BFS01 {
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if (currColor == newColor) {
            return image;
        }
        int n = image.length, m = image[0].length;
        // 队列queue存放是一个数组[x,y] 代表坐标位置
        Queue<int[]> queue = new LinkedList<int[]>();
        // offer 队列里加元素
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor;
        while (!queue.isEmpty()) {
            System.out.println("外层 ==  "+ Arrays.deepToString(queue.toArray()));
            // poll从队列里取出元素并且删除
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                    queue.offer(new int[]{mx, my});
                    image[mx][my] = newColor;
                    System.out.println("内层 =======  "+Arrays.deepToString(queue.toArray()));
                }
            }
        }
        return image;
    }

    public static void main(String[] args) {
        // 创建二维数组
        int[][] image  = {
                {1,1,1},
                {1,1,0},
                {1,0,1}
        };
        BFS01 bfs01 = new BFS01();
        int[][] newImage = bfs01.floodFill(image,1,1,2);
        System.out.println(Arrays.deepToString(newImage));

    }

}
